package ljl.codetop;

import commons.StupidQuestion;

/**
 * 什么也不考察，天生脑瘫才能做出来
 */
@StupidQuestion("非常讨厌的一道煞笔狗屌题")
@Deprecated
public class _31_next_permutation {

    static class tryout {
        /*
         * 123 132
         * 如果整个是倒序的就没有 next 了，就成正的了
         * 321 123
         * 也就是说倒着的不好处理，找到第一个正序的一翻转就行了
         * 比如 12351 反转成 得先找到第一个比递增大的那个数和他交换
         * 先倒着找，找到倒序递减的那个数，3，把后面的数排序，成了 12315
         * 再往后找比 3 大的最小的数，5
         * 交换 3 和 5，就是 12513
         * 如果倒序找，全是递增的，那就整个翻转，不用交换了，也是答案
         * 写吧，写出来算你牛逼
         */

        /**
         * giao! 居然写对了，我很难受！
         *
         * 看这代码，如果不知道目的是什么，就算是我自己写的，我也很难看懂
         * 说明想只通过读代码，想看懂它的含义，是没那么容易的！
         */
        public void nextPermutation(int[] nums) {
            int pos = nums.length - 2;
            while (pos >= 0 && nums[pos] >= nums[pos + 1])
                pos--;
            if (pos >= 0) {
                int larger = nums.length - 1;
                while (nums[larger] <= nums[pos])
                    larger--;
                int t = nums[pos];
                nums[pos] = nums[larger];
                nums[larger] = t;
            }
            // pos 后面的内容整个翻转
            for (int i = pos + 1, j = nums.length - 1; i < j; i++, j--) {
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
            }
        }
    }

    /**
     * 他的更优雅
     */
    static class off1 {
        public void nextPermutation(int[] nums) {
            int i = nums.length - 2;
            while (i >= 0 && nums[i] >= nums[i + 1]) {
                i--;
            }
            if (i >= 0) {
                int j = nums.length - 1;
                while (j >= 0 && nums[i] >= nums[j]) {
                    j--;
                }
                swap(nums, i, j);
            }
            reverse(nums, i + 1);
        }

        public void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }

        public void reverse(int[] nums, int start) {
            int left = start, right = nums.length - 1;
            while (left < right) {
                swap(nums, left, right);
                left++;
                right--;
            }
        }
    }

}
